Chapter 40
3D Skin Surface Meshing

Table of Contents

40.1   Introduction

Skin surfaces, introduced by Edelsbrunner in [Ede99], have a rich and simple combinatorial and geometric structure that makes them suitable for modeling large molecules in biological computing. Meshing such surfaces is often required for further processing of their geometry, like in numerical simulation and visualization.

A skin surface is defined by a set of weighted points (input balls) and a scalar called the shrink factor. If the shrink factor is equal to one, the surface is just the boundary of the union of the input balls. For a shrink factor smaller than one, the skin surface becomes tangent continuous, due to the appearance of patches of spheres and hyperboloids connecting the balls.

This package constructs a mesh isotopic to the skin surface defined by a set of balls and a shrink factor using the algorithm described in [KV05].

An optimized algorithm is implemented for meshing the union of a set of balls.

40.2   Definition of a Skin Surface

This section first briefly reviews skin surfaces. For a more thorough introduction to skin surfaces, we refer to [Ede99] where they were originally introduced.

A skin surface is defined in terms of a finite set of weighted points $$P and a shrink factor $$s, with $$0 s 1. A weighted point $$p=(p,w_p) ³ × corresponds to a ball with center $$p and radius $$sqrt(w_p). A weighted point with zero weight is called an unweighted point.

A pseudo distance between a weighted point $$p = (p,w_P) and an unweighted point $$x is defined as

$$ (p,x) = p-x ² - w_p,

where $$ p-x is the Euclidean distance between $$p and $$x. The ball corresponding to a weighted point $$p is the zero set of $$(p, · ). Note that if $$w_p<0 the radius of the ball is imaginary and the zero-set is empty.

We can take convex combinations of weighted points by taking convex combinations of their distance functions. Figure 40.1 (left) shows weighted points that are obtained as convex combinations of the dashed circles. For further reading on the space of circles and spheres we refer to [Ped70].

Starting from a weighted point $$p=(p,w_P), the shrunk weighted point $$p^s is obtained by taking a convex combination with the unweighted point centered at $$p, formally $$p^s = s p + (1-s) p', with $$p'=(p,0). A simple calculation shows that, $$p^s = (p,s · w_p). The set $$P^s is the set obtained by shrinking every weighted point of $$P by a factor $$s: $$P^s = {p^s p P}. The shrunk weighted points of Figure 40.1 (left) are shown in Figure 40.1 (right).

We now define the skin surface $$skn$$^s(P) associated with a set of weighted points $$P. Consider the set of weighted points obtained by taking the convex hull of the input weighted points. A calculation shows that every weighted point lies within the union of the input balls. Next, we shrink each weighted point in the convex hull with the shrink factor $$s. Hence, we multiply the radius of the corresponding (real) input circles with a factor $$sqrt(s). The skin surface is the boundary of the union of this set of weighted points:

skn$$s(P)

=

{ps p conv$$ (P)}.

Here $$conv$$(P) ³ × is the convex hull of a set of weighted points $$P, whereas $$ denotes the boundary - in $$ ³ - of the union of the corresponding set of balls.

Recall that each weighted point in the convex hull of the input weighted points is contained in the union of the input weighted points. Hence, for a shrink factor equal to one, the skin surface is the boundary of the union of the input weighted points.

By definition of a skin surface, the weights of the input balls (their radius-squared) are shrunk with a factor of $$s and the skin surface wraps around the shrunk input balls. In order to make the skin surface wrap around the (unshrunk) input balls, we can first increase the weights of the input balls by multiplying them with a factor $$1/s and then compute the skin surface.

40.3   The Interface

The interface to the skin surface package consists of one main function, taking a set of weighted points and a shrink factor and outputting the meshed surface. Further, it defines classes and functions and classed used to perform the main steps of the algorithm. There are two global classes Skin_surface_3 and Union_of_balls_3 both of which are models of the concept SkinSurface_3 and there are two functions to extract a mesh of the skin surface (union of balls) from the objects of the aforementioned classes. A final function takes a mesh and the Skin_surface_3 (Union_of_balls_3) object it is constructed from and refines the mesh. This section describes these classes and functions in more detail.

The main function of the skin surface package takes an iterator range of weighted points, a shrink factor and the number of subdivision steps and outputs a mesh in a CGAL::Polyhedron_3:

Where, FT is the number type used by the Weighted_points.

To obtain more control over the algorithm, the different steps can also be performed separately. First, a Skin_surface_3 object is created from an iterator range of weighted points and a shrink factor. Optional arguments are a boolean telling whether the input weighted points should be grown in such a way that the skin surface wraps around the input balls instead of the shrunk input balls.

The template parameter should implement the SkinSurfaceTraits_3 concept. The type WP_iterator, is an iterator over weighted points as defined by SkinSurfaceTraits_3 and FT is the number type used by the weighted points.

For a shrink factor equal to one the skin surface is the boundary of the union of the input balls. In this case the algorithm used for meshing the skin surface greatly simplifies. These optimizations are implemented in the class Union_of_balls_3. The constructor for the union of balls class is similar, except for the missing shrink factor:

With a model of the concept SkinSurface_3 it is possible to generate a coarse mesh isotopic to the skin surface. Using the function mesh_skin_surface_3 with signature:

The last function takes the (coarse) mesh and subdivides it in-situ by applying a given number of 1-4 split operations (each triangle is split into four sub-triangles) and moving the new vertices towards the skin surface. If the number of iterations is not specified, one subdivision step is done. The object of the SkinSurface_3 concept used to construct the coarse mesh is needed to move new points on the skin surface.

40.4   Timings

40.5   Example Programs

40.5.1   Meshing a Skin Surface

File: examples/Skin_surface_3/skin_surface_simple.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/make_skin_surface_mesh_3.h>
#include <list>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_3                                          Bare_point;
typedef CGAL::Weighted_point<Bare_point,K::RT>              Weighted_point;
typedef CGAL::Polyhedron_3<K>                               Polyhedron;

int main() {
  std::list<Weighted_point> l;
  double                    shrinkfactor = 0.5;

  l.push_front(Weighted_point(Bare_point( 1,-1,-1), 1.25));
  l.push_front(Weighted_point(Bare_point( 1, 1, 1), 1.25));
  l.push_front(Weighted_point(Bare_point(-1, 1,-1), 1.25));
  l.push_front(Weighted_point(Bare_point(-1,-1, 1), 1.25));

  Polyhedron p;

  CGAL::make_skin_surface_mesh_3(p, l.begin(), l.end(), shrinkfactor);

  return 0;
}

40.5.2   Meshing and Subdividing a Skin Surface

Next, the coarse mesh is refined to obtain a better approximation. The use of CGAL::Skin_surface_polyhedral_items_3<Skin_surface_3> in the CGAL::Polyhedron is not necessary, but gives the subdivision a significant speedup.

File: examples/Skin_surface_3/skin_surface_subdiv.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Skin_surface_3.h>
#include <CGAL/Polyhedron_3.h>
#include <CGAL/mesh_skin_surface_3.h>
#include <CGAL/subdivide_skin_surface_mesh_3.h>
#include "skin_surface_writer.h"
#include <list>
#include <fstream>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Skin_surface_traits_3<K>                      Traits;
typedef CGAL::Skin_surface_3<Traits>                        Skin_surface_3;
typedef Skin_surface_3::FT                                  FT;
typedef Skin_surface_3::Weighted_point                      Weighted_point;
typedef Weighted_point::Point                               Bare_point;
typedef CGAL::Polyhedron_3<K,
  CGAL::Skin_surface_polyhedral_items_3<Skin_surface_3> >   Polyhedron;

int main() {
  std::list<Weighted_point> l;
  FT                        shrinkfactor = 0.5;

  l.push_front(Weighted_point(Bare_point( 1,-1,-1), 1.25));
  l.push_front(Weighted_point(Bare_point( 1, 1, 1), 1.25));
  l.push_front(Weighted_point(Bare_point(-1, 1,-1), 1.25));
  l.push_front(Weighted_point(Bare_point(-1,-1, 1), 1.25));

  Polyhedron p;

  Skin_surface_3 skin_surface(l.begin(), l.end(), shrinkfactor);
  CGAL::mesh_skin_surface_3(skin_surface, p);

  CGAL::subdivide_skin_surface_mesh_3(skin_surface, p);

  std::ofstream out("mesh.off");
  out << p;

  return 0;
}